﻿<!DOCTYPE html>
<html class="theme theme-white">
<head>
<meta charset="utf-8">
<title>集合相关</title>
<link href="https://www.zybuluo.com/static/assets/template-theme-white.css" rel="stylesheet" media="screen">
<style type="text/css">

#wmd-preview h1  {
    color: #0077bb; /* 将标题改为蓝色 */
}</style>
</head>
<body class="theme theme-white">
<div id="wmd-preview" class="wmd-preview wmd-preview-full-reader"><div class="md-section-divider"></div><div class="md-section-divider"></div><h1 data-anchor-id="5lhd" id="集合相关">集合相关</h1><p data-anchor-id="7r1p"><code>Java面试题</code> <code>集合</code></p><hr><div class="md-section-divider"></div><h3 data-anchor-id="vvjm" id="java中的集合及其继承关系">Java中的集合及其继承关系</h3><p data-anchor-id="c3hy">关于集合的体系是每个人都应该烂熟于心的,尤其是对我们经常使用的List,Map的原理更该如此.这里我们看这张图即可:  <br>
<img src="http://static.zybuluo.com/homiss/jlh96zv6tubp2kazefne2nt9/image_1bk41lrmu11b5gat1a591g4o1hh39.png" alt="image_1bk41lrmu11b5gat1a591g4o1hh39.png-54.2kB" title=""> <br>
更多内容可见集合类总结</p><div class="md-section-divider"></div><h3 data-anchor-id="vl5c" id="poll方法和remove方法区别">poll()方法和remove()方法区别?</h3><p data-anchor-id="cu8b">poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。</p><div class="md-section-divider"></div><h3 data-anchor-id="c4ey" id="linkedhashmap和priorityqueue的区别">LinkedHashMap和PriorityQueue的区别</h3><p data-anchor-id="og5j">PriorityQueue 是一个优先级队列,保证最高或者最低优先级的的元素总是在队列头部，但是 LinkedHashMap 维持的顺序是元素插入的顺序。当遍历一个 PriorityQueue 时，没有任何顺序保证，但是 LinkedHashMap 课保证遍历顺序是元素插入的顺序。</p><div class="md-section-divider"></div><h3 data-anchor-id="6d15" id="weakhashmap与hashmap的区别是什么">WeakHashMap与HashMap的区别是什么?</h3><p data-anchor-id="ufc7">WeakHashMap 的工作与正常的 HashMap 类似，但是使用弱引用作为 key，意思就是当 key 对象没有任何引用时，key/value 将会被回收。</p><div class="md-section-divider"></div><h3 data-anchor-id="3gds" id="arraylist和linkedlist的区别">ArrayList和LinkedList的区别?</h3><p data-anchor-id="eclm">最明显的区别是 ArrrayList底层的数据结构是数组，支持随机访问，而 LinkedList 的底层数据结构是双向循环链表，不支持随机访问。使用下标访问一个元素，ArrayList 的时间复杂度是 O(1)，而 LinkedList 是 O(n)。</p><div class="md-section-divider"></div><h3 data-anchor-id="c5py" id="arraylist和array有什么区别">ArrayList和Array有什么区别?</h3><p data-anchor-id="kzzo">Array可以容纳基本类型和对象，而ArrayList只能容纳对象。</p><p data-anchor-id="mbjs">ArrayList 是Java集合框架类的一员,可以称它为一个动态数组. array 是静态的,所以一个数据一旦创建就无法更改他的大小</p><div class="md-section-divider"></div><h3 data-anchor-id="oh1n" id="arraylist和hashmap默认大小">ArrayList和HashMap默认大小?</h3><p data-anchor-id="0yem">在 java 7 中，ArrayList 的默认大小是 10 个元素，HashMap 的默认大小是16个元素（必须是2的幂）。这就是 Java 7 中 ArrayList 和 HashMap 类的代码片段</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="ojoo"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">private</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> DEFAULT_CAPACITY </span><span class="pun">=</span><span class="pln"> </span><span class="lit">10</span><span class="pun">;</span></code></li><li class="L1"><code class="language-java"></code></li><li class="L2"><code class="language-java"><span class="pln"> </span><span class="com">//from HashMap.java JDK 7</span></code></li><li class="L3"><code class="language-java"><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> DEFAULT_INITIAL_CAPACITY </span><span class="pun">=</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="pun">&lt;&lt;</span><span class="pln"> </span><span class="lit">4</span><span class="pun">;</span><span class="pln"> </span><span class="com">// aka 16</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="ehfp" id="comparator和comparable的区别">Comparator和Comparable的区别?</h3><div class="md-section-divider"></div><h4 data-anchor-id="u47o" id="相同点">相同点</h4><p data-anchor-id="y80h">都是用于比较两个对象“顺序”的接口</p><p data-anchor-id="697p">都可以使用Collections.sort()方法来对对象集合进行排序</p><div class="md-section-divider"></div><h4 data-anchor-id="rfvu" id="不同点">不同点</h4><p data-anchor-id="hrzl">Comparable位于java.lang包下，而Comparator则位于java.util包下</p><p data-anchor-id="ipl2">Comparable 是在集合内部定义的方法实现的排序，Comparator 是在集合外部实现的排序</p><div class="md-section-divider"></div><h4 data-anchor-id="smoe" id="总结">总结</h4><p data-anchor-id="3wl3">使用Comparable接口来实现对象之间的比较时，可以使这个类型（设为A）实现Comparable接口，并可以使用Collections.sort()方法来对A类型的List进行排序，之后可以通过a1.comparaTo(a2)来比较两个对象；</p><p data-anchor-id="gis6">当使用Comparator接口来实现对象之间的比较时，只需要创建一个实现Comparator接口的比较器（设为AComparator），并将其传给Collections.sort()方法即可对A类型的List进行排序，之后也可以通过调用比较器AComparator.compare(a1, a2)来比较两个对象。</p><p data-anchor-id="dmum">可以说一个是自己完成比较，一个是外部程序实现比较的差别而已。</p><p data-anchor-id="m13n">用 Comparator 是策略模式（strategy design pattern），就是不改变对象自身，而用一个策略对象（strategy object）来改变它的行为。</p><p data-anchor-id="7gnd">比如：你想对整数采用绝对值大小来排序，Integer 是不符合要求的，你不需要去修改 Integer 类（实际上你也不能这么做）去改变它的排序行为，这时候只要（也只有）使用一个实现了 Comparator 接口的对象来实现控制它的排序就行了。</p><p data-anchor-id="x6dg">两种方式，各有各的特点：使用Comparable方式比较时，我们将比较的规则写入了比较的类型中，其特点是高内聚。但如果哪天这个规则需要修改，那么我们必须修改这个类型的源代码。如果使用Comparator方式比较，那么我们不需要修改比较的类，其特点是易维护，但需要自定义一个比较器，后续比较规则的修改，仅仅是改这个比较器中的代码即可。</p><div class="md-section-divider"></div><h3 data-anchor-id="16gy" id="如何实现集合排序">如何实现集合排序?</h3><p data-anchor-id="fnqm">你可以使用有序集合，如 TreeSet 或 TreeMap，你也可以使用有顺序的的集合，如 list，然后通过 Collections.sort() 来排序。</p><div class="md-section-divider"></div><h3 data-anchor-id="e8sp" id="如何打印数组内容">如何打印数组内容</h3><p data-anchor-id="k93c">你可以使用 Arrays.toString() 和 Arrays.deepToString() 方法来打印数组。由于数组没有实现 toString() 方法，所以如果将数组传递给 System.out.println() 方法，将无法打印出数组的内容，但是 Arrays.toString() 可以打印每个元素。</p><div class="md-section-divider"></div><h3 data-anchor-id="j1xy" id="linkedlist的是单向链表还是双向">LinkedList的是单向链表还是双向?</h3><p data-anchor-id="g1xv">双向循环列表,具体实现自行查阅源码.</p><div class="md-section-divider"></div><h3 data-anchor-id="9wdr" id="treemap是实现原理">TreeMap是实现原理</h3><p data-anchor-id="bu7q">TreeMap是一个通过红黑树实现有序的key-value集合。</p><p data-anchor-id="3h6u">TreeMap继承AbstractMap，也即实现了Map，它是一个Map集合</p><p data-anchor-id="db6o">TreeMap实现了NavigableMap接口，它支持一系列的导航方法，</p><p data-anchor-id="bjgo">TreeMap实现了Cloneable接口，它可以被克隆</p><p data-anchor-id="7lrc">TreeMap本质是Red-Black Tree，它包含几个重要的成员变量：root、size、comparator。其中root是红黑树的根节点。它是Entry类型，Entry是红黑树的节点，它包含了红黑树的6个基本组成：key、value、left、right、parent和color。Entry节点根据根据Key排序，包含的内容是value。Entry中key比较大小是根据比较器comparator来进行判断的。size是红黑树的节点个数。</p><div class="md-section-divider"></div><h3 data-anchor-id="7gv2" id="遍历arraylist时如何正确移除一个元素">遍历ArrayList时如何正确移除一个元素</h3><p data-anchor-id="6yd4">错误写法示例一：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="cbt9"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> remove</span><span class="pun">(</span><span class="typ">ArrayList</span><span class="pun">&lt;</span><span class="typ">String</span><span class="pun">&gt;</span><span class="pln"> list</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;</span><span class="pln"> list</span><span class="pun">.</span><span class="pln">size</span><span class="pun">();</span><span class="pln"> i</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L2"><code class="language-java"><span class="pln">        </span><span class="typ">String</span><span class="pln"> s </span><span class="pun">=</span><span class="pln"> list</span><span class="pun">.</span><span class="pln">get</span><span class="pun">(</span><span class="pln">i</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L3"><code class="language-java"><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="str">"bb"</span><span class="pun">))</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L4"><code class="language-java"><span class="pln">            list</span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">s</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L5"><code class="language-java"><span class="pln">        </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L6"><code class="language-java"><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L7"><code class="language-java"><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><p data-anchor-id="l9hw">错误写法示例二：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="txgb"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> remove</span><span class="pun">(</span><span class="typ">ArrayList</span><span class="pun">&lt;</span><span class="typ">String</span><span class="pun">&gt;</span><span class="pln"> list</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="typ">String</span><span class="pln"> s </span><span class="pun">:</span><span class="pln"> list</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="str">"bb"</span><span class="pun">))</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">            list</span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">s</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pun">}</span><span class="pln"> </span></code></li></ol></pre><p data-anchor-id="gyyy">要分析产生上述错误现象的原因唯有翻一翻jdk的ArrayList源码，先看下ArrayList中的remove方法（注意ArrayList中的remove有两个同名方法，只是入参不同，这里看的是入参为Object的remove方法）是怎么实现的：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="z7wm"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">boolean</span><span class="pln"> remove</span><span class="pun">(</span><span class="typ">Object</span><span class="pln"> o</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">o </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">        </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> index </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> index </span><span class="pun">&lt;</span><span class="pln"> size</span><span class="pun">;</span><span class="pln"> index</span><span class="pun">++)</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">            </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">elementData</span><span class="pun">[</span><span class="pln">index</span><span class="pun">]</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">                fastRemove</span><span class="pun">(</span><span class="pln">index</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">                </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">true</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">            </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln">    </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pln">        </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> index </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> index </span><span class="pun">&lt;</span><span class="pln"> size</span><span class="pun">;</span><span class="pln"> index</span><span class="pun">++)</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pln">            </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">o</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="pln">elementData</span><span class="pun">[</span><span class="pln">index</span><span class="pun">]))</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L0"><code><span class="pln">                fastRemove</span><span class="pun">(</span><span class="pln">index</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">                </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">true</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">            </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">false</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><p data-anchor-id="agze">按一般执行路径会走到else路径下最终调用faseRemove方法：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="rfq9"><ol class="linenums"><li class="L0"><code><span class="kwd">private</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> fastRemove</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> index</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    modCount</span><span class="pun">++;</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">int</span><span class="pln"> numMoved </span><span class="pun">=</span><span class="pln"> size </span><span class="pun">-</span><span class="pln"> index </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">numMoved </span><span class="pun">&gt;</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">        </span><span class="typ">System</span><span class="pun">.</span><span class="pln">arraycopy</span><span class="pun">(</span><span class="pln">elementData</span><span class="pun">,</span><span class="pln"> index</span><span class="pun">+</span><span class="lit">1</span><span class="pun">,</span><span class="pln"> elementData</span><span class="pun">,</span><span class="pln"> index</span><span class="pun">,</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">                         numMoved</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">    elementData</span><span class="pun">[--</span><span class="pln">size</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln"> </span><span class="com">// Let gc do its work  </span></code></li><li class="L7"><code><span class="pun">}</span><span class="pln"> </span></code></li></ol></pre><p data-anchor-id="65xj">可以看到会执行System.arraycopy方法，导致删除元素时涉及到数组元素的移动。针对错误写法一，在遍历第二个元素字符串bb时因为符合删除条件，所以将该元素从数组中删除，并且将后一个元素移动（也是字符串bb）至当前位置，导致下一次循环遍历时后一个字符串bb并没有遍历到，所以无法删除。 <br>
针对这种情况可以倒序删除的方式来避免：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="9obh"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> remove</span><span class="pun">(</span><span class="typ">ArrayList</span><span class="pun">&lt;</span><span class="typ">String</span><span class="pun">&gt;</span><span class="pln"> list</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> list</span><span class="pun">.</span><span class="pln">size</span><span class="pun">()</span><span class="pln"> </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&gt;=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> i</span><span class="pun">--)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">        </span><span class="typ">String</span><span class="pln"> s </span><span class="pun">=</span><span class="pln"> list</span><span class="pun">.</span><span class="kwd">get</span><span class="pun">(</span><span class="pln">i</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="str">"bb"</span><span class="pun">))</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">            list</span><span class="pun">.</span><span class="pln">remove</span><span class="pun">(</span><span class="pln">s</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pun">}</span><span class="pln"> </span></code></li></ol></pre><p data-anchor-id="1e9z">因为数组倒序遍历时即使发生元素删除也不影响后序元素遍历。</p><p data-anchor-id="e59u">而错误二产生的原因却是foreach写法是对实际的Iterable、hasNext、next方法的简写，问题同样处在上文的fastRemove方法中，可以看到第一行把modCount变量的值加一，但在ArrayList返回的迭代器（该代码在其父类AbstractList中）：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="pzoc"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="typ">Iterator</span><span class="pun">&lt;</span><span class="pln">E</span><span class="pun">&gt;</span><span class="pln"> iterator</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">Itr</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><p data-anchor-id="nxz1">这里返回的是AbstractList类内部的迭代器实现private class Itr implements Iterator，看这个类的next方法：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="52no"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> E </span><span class="kwd">next</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    checkForComodification</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">try</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">        E </span><span class="kwd">next</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">get</span><span class="pun">(</span><span class="pln">cursor</span><span class="pun">);</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">        lastRet </span><span class="pun">=</span><span class="pln"> cursor</span><span class="pun">++;</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">        </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">next</span><span class="pun">;</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">    </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">catch</span><span class="pln"> </span><span class="pun">(</span><span class="typ">IndexOutOfBoundsException</span><span class="pln"> e</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln">        checkForComodification</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pln">        </span><span class="kwd">throw</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">NoSuchElementException</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L9"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L0"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><p data-anchor-id="mq9e">第一行checkForComodification方法：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="tszo"><ol class="linenums"><li class="L0"><code><span class="kwd">final</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> checkForComodification</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">modCount </span><span class="pun">!=</span><span class="pln"> expectedModCount</span><span class="pun">)</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">        </span><span class="kwd">throw</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ConcurrentModificationException</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pun">}</span><span class="pln">  </span></code></li></ol></pre><p data-anchor-id="pj3v">这里会做迭代器内部修改次数检查，因为上面的remove(Object)方法把修改了modCount的值，所以才会报出并发修改异常。要避免这种情况的出现则在使用迭代器迭代时（显示或foreach的隐式）不要使用ArrayList的remove，改为用Iterator的remove即可。</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="dqwz"><ol class="linenums"><li class="L0"><code><span class="kwd">public</span><span class="pln"> </span><span class="kwd">static</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> remove</span><span class="pun">(</span><span class="typ">ArrayList</span><span class="pun">&lt;</span><span class="typ">String</span><span class="pun">&gt;</span><span class="pln"> list</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L1"><code><span class="pln">    </span><span class="typ">Iterator</span><span class="pun">&lt;</span><span class="typ">String</span><span class="pun">&gt;</span><span class="pln"> it </span><span class="pun">=</span><span class="pln"> list</span><span class="pun">.</span><span class="pln">iterator</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L2"><code><span class="pln">    </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="pln">it</span><span class="pun">.</span><span class="pln">hasNext</span><span class="pun">())</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L3"><code><span class="pln">        </span><span class="typ">String</span><span class="pln"> s </span><span class="pun">=</span><span class="pln"> it</span><span class="pun">.</span><span class="kwd">next</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L4"><code><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="str">"bb"</span><span class="pun">))</span><span class="pln"> </span><span class="pun">{</span><span class="pln">  </span></code></li><li class="L5"><code><span class="pln">            it</span><span class="pun">.</span><span class="pln">remove</span><span class="pun">();</span><span class="pln">  </span></code></li><li class="L6"><code><span class="pln">        </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L7"><code><span class="pln">    </span><span class="pun">}</span><span class="pln">  </span></code></li><li class="L8"><code><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h3 data-anchor-id="kyeo" id="hashmap的实现原理">HashMap的实现原理</h3><p data-anchor-id="ap9z">HashMap是基于哈希表实现的map，哈希表（也叫关联数组）一种通用的数据结构，是Java开发者常用的类，常用来存储和获取数据，功能强大使用起来也很方便，是居家旅行...不对，是Java开发需要掌握的基本技能，也是面试必考的知识点，所以，了解HashMap是很有必要的。</p><div class="md-section-divider"></div><h4 data-anchor-id="maai" id="原理">原理</h4><p data-anchor-id="0ydq">简单讲解下HashMap的原理：HashMap基于Hash算法，我们通过put(key,value)存储，get(key)来获取。当传入key时，HashMap会根据key.hashCode()计算出hash值，根据hash值将value保存在bucket里。当计算出的hash值相同时怎么办呢，我们称之为Hash冲突，HashMap的做法是用链表和红黑树存储相同hash值的value。当Hash冲突的个数比较少时，使用链表，否则使用红黑树。</p><div class="md-section-divider"></div><h4 data-anchor-id="qyz5" id="内部存储结构">内部存储结构</h4><p data-anchor-id="vlti">HashMap类实现了Map&lt; K, V&gt;接口，主要包含以下几个方法：</p><ul data-anchor-id="ux72">
<li>V put(K key, V value)</li>
<li>V get(Object key)</li>
<li>V remove(Object key)</li>
<li>Boolean containsKey(Object key)</li>
</ul><p data-anchor-id="qhpq">HashMap使用了一个内部类Node&lt; K, V&gt;来存储数据</p><blockquote data-anchor-id="mrbi" class="white-blockquote">
  <p>我阅读的是Java 8的源码，在Java 8之前存储数据的内部类是Entry&lt; K, V&gt;，代码大体都是一样的</p>
</blockquote><p data-anchor-id="1ryt">Node代码：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="x4rb"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">class</span><span class="pln"> </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> </span><span class="kwd">implements</span><span class="pln"> </span><span class="typ">Map</span><span class="pun">.</span><span class="typ">Entry</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> hash</span><span class="pun">;</span></code></li><li class="L2"><code class="language-java"><span class="pln">    </span><span class="kwd">final</span><span class="pln"> K key</span><span class="pun">;</span></code></li><li class="L3"><code class="language-java"><span class="pln">    V value</span><span class="pun">;</span></code></li><li class="L4"><code class="language-java"><span class="pln">    </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> next</span><span class="pun">;</span></code></li><li class="L5"><code class="language-java"><span class="pln">    </span><span class="pun">...</span></code></li><li class="L6"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="rirn">可以看见Node类中除了键值对（key-value）以外，还有额外的两个数据：</p><ul data-anchor-id="qjs8">
<li>hash : 这个是通过计算得到的散列值</li>
<li>next：指向另一个Node，这样HashMap可以像链表一样存储数据</li>
</ul><p data-anchor-id="c3nk">因此可以知道，HashMap的结构大致如下：</p><p data-anchor-id="xy2u"><img src="http://7pulh4.com1.z0.glb.clouddn.com/HashMap%E6%BA%90%E7%A0%81%E9%98%85%E8%AF%BB1.jpg" alt="HashMap源码阅读1" title=""></p><p data-anchor-id="u31v">我们可以将每个横向看成一个个的桶，每个桶中存放着具有相同Hash值的Node,通过一个list来存放每个桶。</p><div class="md-section-divider"></div><h4 data-anchor-id="f55y" id="内部变量">内部变量</h4><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="updn"><ol class="linenums"><li class="L0"><code class="language-java"><span class="com">// 默认容量大小</span></code></li><li class="L1"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> DEFAULT_INITIAL_CAPACITY </span><span class="pun">=</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="pun">&lt;&lt;</span><span class="pln"> </span><span class="lit">4</span><span class="pun">;</span><span class="pln"> </span><span class="com">// aka 16</span></code></li><li class="L2"><code class="language-java"><span class="com">// 最大容量</span></code></li><li class="L3"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> MAXIMUM_CAPACITY </span><span class="pun">=</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="pun">&lt;&lt;</span><span class="pln"> </span><span class="lit">30</span><span class="pun">;</span></code></li><li class="L4"><code class="language-java"><span class="com">// 装载因子</span></code></li><li class="L5"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">float</span><span class="pln"> DEFAULT_LOAD_FACTOR </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0.75f</span><span class="pun">;</span></code></li><li class="L6"><code class="language-java"><span class="com">// 转换为二叉树的阀值</span></code></li><li class="L7"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> TREEIFY_THRESHOLD </span><span class="pun">=</span><span class="pln"> </span><span class="lit">8</span><span class="pun">;</span></code></li><li class="L8"><code class="language-java"><span class="com">// 转换为二叉树的最低阀值</span></code></li><li class="L9"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> UNTREEIFY_THRESHOLD </span><span class="pun">=</span><span class="pln"> </span><span class="lit">6</span><span class="pun">;</span></code></li><li class="L0"><code class="language-java"><span class="com">// 二叉树最小容量</span></code></li><li class="L1"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> MIN_TREEIFY_CAPACITY </span><span class="pun">=</span><span class="pln"> </span><span class="lit">64</span><span class="pun">;</span></code></li><li class="L2"><code class="language-java"><span class="com">// 哈希表</span></code></li><li class="L3"><code class="language-java"><span class="kwd">transient</span><span class="pln"> </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;[]</span><span class="pln"> table</span><span class="pun">;</span></code></li><li class="L4"><code class="language-java"><span class="com">// 键值对的数量</span></code></li><li class="L5"><code class="language-java"><span class="kwd">transient</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> size</span><span class="pun">;</span></code></li><li class="L6"><code class="language-java"><span class="com">// 记录HashMap结构改变次数，与HashMap的快速失败相关</span></code></li><li class="L7"><code class="language-java"><span class="kwd">transient</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> modCount</span><span class="pun">;</span></code></li><li class="L8"><code class="language-java"><span class="com">// 扩容的阈值</span></code></li><li class="L9"><code class="language-java"><span class="kwd">int</span><span class="pln"> threshold</span><span class="pun">;</span></code></li><li class="L0"><code class="language-java"><span class="com">// 装载因子</span></code></li><li class="L1"><code class="language-java"><span class="kwd">final</span><span class="pln"> </span><span class="kwd">float</span><span class="pln"> loadFactor</span><span class="pun">;</span></code></li></ol></pre><div class="md-section-divider"></div><h4 data-anchor-id="2h63" id="常用方法">常用方法</h4><div class="md-section-divider"></div><h5 data-anchor-id="iok0" id="put操作">put操作</h5><p data-anchor-id="kemt">put函数大致的思路为：</p><ol data-anchor-id="mqcb">
<li>对key的hashCode()做hash，然后再计算index;</li>
<li>如果没碰撞直接放到bucket里；</li>
<li>如果碰撞了，以链表的形式存在buckets后；</li>
<li>如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；</li>
<li>如果节点已经存在就替换old value(保证key的唯一性)</li>
<li>如果bucket满了(超过load factor*current capacity)，就要resize。</li>
</ol><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="uy85"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">public</span><span class="pln"> V put</span><span class="pun">(</span><span class="pln">K key</span><span class="pun">,</span><span class="pln"> V value</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="kwd">return</span><span class="pln"> putVal</span><span class="pun">(</span><span class="pln">hash</span><span class="pun">(</span><span class="pln">key</span><span class="pun">),</span><span class="pln"> key</span><span class="pun">,</span><span class="pln"> value</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">false</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">true</span><span class="pun">);</span></code></li><li class="L2"><code class="language-java"><span class="pun">}</span></code></li><li class="L3"><code class="language-java"></code></li><li class="L4"><code class="language-java"><span class="kwd">final</span><span class="pln"> V putVal</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> hash</span><span class="pun">,</span><span class="pln"> K key</span><span class="pun">,</span><span class="pln"> V value</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">boolean</span><span class="pln"> onlyIfAbsent</span><span class="pun">,</span></code></li><li class="L5"><code class="language-java"><span class="pln">                   </span><span class="kwd">boolean</span><span class="pln"> evict</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code class="language-java"><span class="pln">    </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;[]</span><span class="pln"> tab</span><span class="pun">;</span><span class="pln"> </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> p</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> n</span><span class="pun">,</span><span class="pln"> i</span><span class="pun">;</span></code></li><li class="L7"><code class="language-java"><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">((</span><span class="pln">tab </span><span class="pun">=</span><span class="pln"> table</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">||</span><span class="pln"> </span><span class="pun">(</span><span class="pln">n </span><span class="pun">=</span><span class="pln"> tab</span><span class="pun">.</span><span class="pln">length</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span></code></li><li class="L8"><code class="language-java"><span class="pln">        n </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">tab </span><span class="pun">=</span><span class="pln"> resize</span><span class="pun">()).</span><span class="pln">length</span><span class="pun">;</span><span class="pln"> </span><span class="com">// resize()是调整table数组大小的，如果table数组为空或长度为0，重新调整大小</span></code></li><li class="L9"><code class="language-java"><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">((</span><span class="pln">p </span><span class="pun">=</span><span class="pln"> tab</span><span class="pun">[</span><span class="pln">i </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">n </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">)</span><span class="pln"> </span><span class="pun">&amp;</span><span class="pln"> hash</span><span class="pun">])</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="com">// i = (n - 1) &amp; hash | 这里计算出来的i值就是存放数组的位置，如果当前位置为空，则直接放入其中</span></code></li><li class="L0"><code class="language-java"><span class="pln">        tab</span><span class="pun">[</span><span class="pln">i</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> newNode</span><span class="pun">(</span><span class="pln">hash</span><span class="pun">,</span><span class="pln"> key</span><span class="pun">,</span><span class="pln"> value</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">);</span></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="kwd">else</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="com">// hash冲突</span></code></li><li class="L2"><code class="language-java"><span class="pln">        </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> e</span><span class="pun">;</span><span class="pln"> K k</span><span class="pun">;</span></code></li><li class="L3"><code class="language-java"><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">p</span><span class="pun">.</span><span class="pln">hash </span><span class="pun">==</span><span class="pln"> hash </span><span class="pun">&amp;&amp;</span></code></li><li class="L4"><code class="language-java"><span class="pln">            </span><span class="pun">((</span><span class="pln">k </span><span class="pun">=</span><span class="pln"> p</span><span class="pun">.</span><span class="pln">key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> key </span><span class="pun">||</span><span class="pln"> </span><span class="pun">(</span><span class="pln">key </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> key</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="pln">k</span><span class="pun">))))</span><span class="pln"> </span><span class="com">// 如果hash相同，并且key值也相同，则找到存放位置</span></code></li><li class="L5"><code class="language-java"><span class="pln">            e </span><span class="pun">=</span><span class="pln"> p</span><span class="pun">;</span></code></li><li class="L6"><code class="language-java"><span class="pln">        </span><span class="kwd">else</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">p </span><span class="kwd">instanceof</span><span class="pln"> </span><span class="typ">TreeNode</span><span class="pun">)</span><span class="pln"> </span><span class="com">// 如果当前p是二叉树，则放入二叉树中</span></code></li><li class="L7"><code class="language-java"><span class="pln">            e </span><span class="pun">=</span><span class="pln"> </span><span class="pun">((</span><span class="typ">TreeNode</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;)</span><span class="pln">p</span><span class="pun">).</span><span class="pln">putTreeVal</span><span class="pun">(</span><span class="kwd">this</span><span class="pun">,</span><span class="pln"> tab</span><span class="pun">,</span><span class="pln"> hash</span><span class="pun">,</span><span class="pln"> key</span><span class="pun">,</span><span class="pln"> value</span><span class="pun">);</span></code></li><li class="L8"><code class="language-java"><span class="pln">        </span><span class="kwd">else</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="com">// 存放到链表中</span></code></li><li class="L9"><code class="language-java"><span class="pln">            </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> binCount </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> </span><span class="pun">;</span><span class="pln"> </span><span class="pun">++</span><span class="pln">binCount</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L0"><code class="language-java"><span class="pln">                </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">((</span><span class="pln">e </span><span class="pun">=</span><span class="pln"> p</span><span class="pun">.</span><span class="pln">next</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="com">// 遍历链表并将值放到链表最后</span></code></li><li class="L1"><code class="language-java"><span class="pln">                    p</span><span class="pun">.</span><span class="pln">next </span><span class="pun">=</span><span class="pln"> newNode</span><span class="pun">(</span><span class="pln">hash</span><span class="pun">,</span><span class="pln"> key</span><span class="pun">,</span><span class="pln"> value</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">);</span></code></li><li class="L2"><code class="language-java"><span class="pln">                    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">binCount </span><span class="pun">&gt;=</span><span class="pln"> TREEIFY_THRESHOLD </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">)</span><span class="pln"> </span><span class="com">// -1 for 1st</span></code></li><li class="L3"><code class="language-java"><span class="pln">                        treeifyBin</span><span class="pun">(</span><span class="pln">tab</span><span class="pun">,</span><span class="pln"> hash</span><span class="pun">);</span><span class="pln"> </span><span class="com">// 如果链表中的值大于TREEIFY_THRESHOLD - 1，则将链表转换成二叉树</span></code></li><li class="L4"><code class="language-java"><span class="pln">                    </span><span class="kwd">break</span><span class="pun">;</span></code></li><li class="L5"><code class="language-java"><span class="pln">                </span><span class="pun">}</span></code></li><li class="L6"><code class="language-java"><span class="pln">                </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">e</span><span class="pun">.</span><span class="pln">hash </span><span class="pun">==</span><span class="pln"> hash </span><span class="pun">&amp;&amp;</span></code></li><li class="L7"><code class="language-java"><span class="pln">                    </span><span class="pun">((</span><span class="pln">k </span><span class="pun">=</span><span class="pln"> e</span><span class="pun">.</span><span class="pln">key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> key </span><span class="pun">||</span><span class="pln"> </span><span class="pun">(</span><span class="pln">key </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> key</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="pln">k</span><span class="pun">))))</span></code></li><li class="L8"><code class="language-java"><span class="pln">                    </span><span class="kwd">break</span><span class="pun">;</span></code></li><li class="L9"><code class="language-java"><span class="pln">                p </span><span class="pun">=</span><span class="pln"> e</span><span class="pun">;</span></code></li><li class="L0"><code class="language-java"><span class="pln">            </span><span class="pun">}</span></code></li><li class="L1"><code class="language-java"><span class="pln">        </span><span class="pun">}</span></code></li><li class="L2"><code class="language-java"><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">e </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="com">// 表示对于当前key早已经存在</span></code></li><li class="L3"><code class="language-java"><span class="pln">            V oldValue </span><span class="pun">=</span><span class="pln"> e</span><span class="pun">.</span><span class="pln">value</span><span class="pun">;</span></code></li><li class="L4"><code class="language-java"><span class="pln">            </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(!</span><span class="pln">onlyIfAbsent </span><span class="pun">||</span><span class="pln"> oldValue </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="com">// 如果onlyIfAbsent为false或则oldValue为空，替换原来的值</span></code></li><li class="L5"><code class="language-java"><span class="pln">                e</span><span class="pun">.</span><span class="pln">value </span><span class="pun">=</span><span class="pln"> value</span><span class="pun">;</span></code></li><li class="L6"><code class="language-java"><span class="pln">            afterNodeAccess</span><span class="pun">(</span><span class="pln">e</span><span class="pun">);</span></code></li><li class="L7"><code class="language-java"><span class="pln">            </span><span class="kwd">return</span><span class="pln"> oldValue</span><span class="pun">;</span><span class="pln"> </span><span class="com">// 返回原来的值</span></code></li><li class="L8"><code class="language-java"><span class="pln">        </span><span class="pun">}</span></code></li><li class="L9"><code class="language-java"><span class="pln">    </span><span class="pun">}</span></code></li><li class="L0"><code class="language-java"><span class="pln">    </span><span class="pun">++</span><span class="pln">modCount</span><span class="pun">;</span><span class="pln"> </span><span class="com">// HashMap结构修改次数，主要用于判断迭代器中fail-fast</span></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(++</span><span class="pln">size </span><span class="pun">&gt;</span><span class="pln"> threshold</span><span class="pun">)</span><span class="pln"> </span><span class="com">// 如果++size后的值比阀值大，则重新调整大小</span></code></li><li class="L2"><code class="language-java"><span class="pln">        resize</span><span class="pun">();</span></code></li><li class="L3"><code class="language-java"><span class="pln">    afterNodeInsertion</span><span class="pun">(</span><span class="pln">evict</span><span class="pun">);</span></code></li><li class="L4"><code class="language-java"><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span></code></li><li class="L5"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="idel">代码也比较容易看懂，值得注意的就是</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="5mto"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">else</span><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">p </span><span class="kwd">instanceof</span><span class="pln"> </span><span class="typ">TreeNode</span><span class="pun">)</span><span class="pln"> </span><span class="com">// 如果当前p是二叉树，则放入二叉树中</span></code></li><li class="L1"><code class="language-java"><span class="pln">     e </span><span class="pun">=</span><span class="pln"> </span><span class="pun">((</span><span class="typ">TreeNode</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;)</span><span class="pln">p</span><span class="pun">).</span><span class="pln">putTreeVal</span><span class="pun">(</span><span class="kwd">this</span><span class="pun">,</span><span class="pln"> tab</span><span class="pun">,</span><span class="pln"> hash</span><span class="pun">,</span><span class="pln"> key</span><span class="pun">,</span><span class="pln"> value</span><span class="pun">);</span></code></li></ol></pre><p data-anchor-id="yk2j">与</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="y7in"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">binCount </span><span class="pun">&gt;=</span><span class="pln"> TREEIFY_THRESHOLD </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">)</span><span class="pln"> </span><span class="com">// -1 for 1st</span></code></li><li class="L1"><code class="language-java"><span class="pln">    treeifyBin</span><span class="pun">(</span><span class="pln">tab</span><span class="pun">,</span><span class="pln"> hash</span><span class="pun">);</span><span class="pln"> </span><span class="com">// 如果链表中的值大于TREEIFY_THRESHOLD - 1，则将链表转换成二叉树</span></code></li></ol></pre><p data-anchor-id="aiyu">这是Java 8相对于以前版本一个比较大的改变。</p><p data-anchor-id="h9vp">在Java 8以前，每次产生hash冲突，就将记录追加到链表后面，然后通过遍历链表来查找。如果某个链表中记录过大，每次遍历的数据就越多，效率也就很低，复杂度为O(n)；</p><p data-anchor-id="562b">在Java 8中，加入了一个常量TREEIFY_THRESHOLD=8，如果某个链表中的记录大于这个常量的话，HashMap会动态的使用一个专门的treemap实现来替换掉它。这样复杂度是O(logn)，比链表的O(n)会好很多。</p><p data-anchor-id="zkkz">对于前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。</p><div class="md-section-divider"></div><h5 data-anchor-id="3iuf" id="get操作">get操作</h5><p data-anchor-id="71mu">在理解了put之后，get就很简单了。大致思路如下： <br>
1. bucket里的第一个节点，直接命中； <br>
2. 如果有冲突，则通过key.equals(k)去查找对应的entry <br>
3. 若为树，则在树中通过key.equals(k)查找，O(logn)； <br>
4. 若为链表，则在链表中通过key.equals(k)查找，O(n)。</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="32ym"><ol class="linenums"><li class="L0"><code class="language-java"><span class="kwd">public</span><span class="pln"> V get</span><span class="pun">(</span><span class="typ">Object</span><span class="pln"> key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> e</span><span class="pun">;</span></code></li><li class="L2"><code class="language-java"><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">(</span><span class="pln">e </span><span class="pun">=</span><span class="pln"> getNode</span><span class="pun">(</span><span class="pln">hash</span><span class="pun">(</span><span class="pln">key</span><span class="pun">),</span><span class="pln"> key</span><span class="pun">))</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">?</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">:</span><span class="pln"> e</span><span class="pun">.</span><span class="pln">value</span><span class="pun">;</span></code></li><li class="L3"><code class="language-java"><span class="pun">}</span></code></li><li class="L4"><code class="language-java"></code></li><li class="L5"><code class="language-java"><span class="kwd">final</span><span class="pln"> </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> getNode</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> hash</span><span class="pun">,</span><span class="pln"> </span><span class="typ">Object</span><span class="pln"> key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code class="language-java"><span class="pln">    </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;[]</span><span class="pln"> tab</span><span class="pun">;</span><span class="pln"> </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> first</span><span class="pun">,</span><span class="pln"> e</span><span class="pun">;</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> K k</span><span class="pun">;</span></code></li><li class="L7"><code class="language-java"><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">((</span><span class="pln">tab </span><span class="pun">=</span><span class="pln"> table</span><span class="pun">)</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> </span><span class="pun">(</span><span class="pln">n </span><span class="pun">=</span><span class="pln"> tab</span><span class="pun">.</span><span class="pln">length</span><span class="pun">)</span><span class="pln"> </span><span class="pun">&gt;</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">&amp;&amp;</span></code></li><li class="L8"><code class="language-java"><span class="pln">        </span><span class="pun">(</span><span class="pln">first </span><span class="pun">=</span><span class="pln"> tab</span><span class="pun">[(</span><span class="pln">n </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">)</span><span class="pln"> </span><span class="pun">&amp;</span><span class="pln"> hash</span><span class="pun">])</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L9"><code class="language-java"><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">first</span><span class="pun">.</span><span class="pln">hash </span><span class="pun">==</span><span class="pln"> hash </span><span class="pun">&amp;&amp;</span><span class="pln"> </span><span class="com">// always check first node</span></code></li><li class="L0"><code class="language-java"><span class="pln">            </span><span class="pun">((</span><span class="pln">k </span><span class="pun">=</span><span class="pln"> first</span><span class="pun">.</span><span class="pln">key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> key </span><span class="pun">||</span><span class="pln"> </span><span class="pun">(</span><span class="pln">key </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> key</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="pln">k</span><span class="pun">))))</span><span class="pln"> </span><span class="com">// 如果hash相同并且key值一样则返回当前node</span></code></li><li class="L1"><code class="language-java"><span class="pln">            </span><span class="kwd">return</span><span class="pln"> first</span><span class="pun">;</span></code></li><li class="L2"><code class="language-java"><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">((</span><span class="pln">e </span><span class="pun">=</span><span class="pln"> first</span><span class="pun">.</span><span class="pln">next</span><span class="pun">)</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span></code></li><li class="L3"><code class="language-java"><span class="pln">            </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">first </span><span class="kwd">instanceof</span><span class="pln"> </span><span class="typ">TreeNode</span><span class="pun">)</span><span class="pln"> </span><span class="com">// 如果当前node为二叉树，则在二叉树中查找</span></code></li><li class="L4"><code class="language-java"><span class="pln">                </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">((</span><span class="typ">TreeNode</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;)</span><span class="pln">first</span><span class="pun">).</span><span class="pln">getTreeNode</span><span class="pun">(</span><span class="pln">hash</span><span class="pun">,</span><span class="pln"> key</span><span class="pun">);</span></code></li><li class="L5"><code class="language-java"><span class="pln">            </span><span class="kwd">do</span><span class="pln"> </span><span class="pun">{</span><span class="pln"> </span><span class="com">// 遍历链表</span></code></li><li class="L6"><code class="language-java"><span class="pln">                </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">e</span><span class="pun">.</span><span class="pln">hash </span><span class="pun">==</span><span class="pln"> hash </span><span class="pun">&amp;&amp;</span></code></li><li class="L7"><code class="language-java"><span class="pln">                    </span><span class="pun">((</span><span class="pln">k </span><span class="pun">=</span><span class="pln"> e</span><span class="pun">.</span><span class="pln">key</span><span class="pun">)</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> key </span><span class="pun">||</span><span class="pln"> </span><span class="pun">(</span><span class="pln">key </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> key</span><span class="pun">.</span><span class="pln">equals</span><span class="pun">(</span><span class="pln">k</span><span class="pun">))))</span></code></li><li class="L8"><code class="language-java"><span class="pln">                    </span><span class="kwd">return</span><span class="pln"> e</span><span class="pun">;</span></code></li><li class="L9"><code class="language-java"><span class="pln">            </span><span class="pun">}</span><span class="pln"> </span><span class="kwd">while</span><span class="pln"> </span><span class="pun">((</span><span class="pln">e </span><span class="pun">=</span><span class="pln"> e</span><span class="pun">.</span><span class="pln">next</span><span class="pun">)</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">);</span></code></li><li class="L0"><code class="language-java"><span class="pln">        </span><span class="pun">}</span></code></li><li class="L1"><code class="language-java"><span class="pln">    </span><span class="pun">}</span></code></li><li class="L2"><code class="language-java"><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span></code></li><li class="L3"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h4 data-anchor-id="n7ph" id="自动扩容">自动扩容</h4><p data-anchor-id="ccib">如果在初始化HashMap中没有指定初始容量，那么默认容量为16，但是如果后来HashMap中存放的数量超过了16，那么便会有大量的hash冲突；在HashMap中有自动扩容机制，如果当前存放的数量大于某个界限，HashMap便会调用resize()方法，扩大HashMap的容量。</p><p data-anchor-id="7pxg">当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。</p><p data-anchor-id="v6bb">HashMap的capacity必须满足是2的N次方,如果在构造函数内指定的容量n不满足,HashMap会通过下面的算法将其转换为大于n的最小的2的N次方数。</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="wmcx"><ol class="linenums"><li class="L0"><code class="language-java"><span class="com">// 减1→移位→按位或运算→加1返回</span></code></li><li class="L1"><code class="language-java"><span class="kwd">static</span><span class="pln"> </span><span class="kwd">final</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> tableSizeFor</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> cap</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L2"><code class="language-java"><span class="pln">    </span><span class="kwd">int</span><span class="pln"> n </span><span class="pun">=</span><span class="pln"> cap </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span></code></li><li class="L3"><code class="language-java"><span class="pln">    n </span><span class="pun">|=</span><span class="pln"> n </span><span class="pun">&gt;&gt;&gt;</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span></code></li><li class="L4"><code class="language-java"><span class="pln">    n </span><span class="pun">|=</span><span class="pln"> n </span><span class="pun">&gt;&gt;&gt;</span><span class="pln"> </span><span class="lit">2</span><span class="pun">;</span></code></li><li class="L5"><code class="language-java"><span class="pln">    n </span><span class="pun">|=</span><span class="pln"> n </span><span class="pun">&gt;&gt;&gt;</span><span class="pln"> </span><span class="lit">4</span><span class="pun">;</span></code></li><li class="L6"><code class="language-java"><span class="pln">    n </span><span class="pun">|=</span><span class="pln"> n </span><span class="pun">&gt;&gt;&gt;</span><span class="pln"> </span><span class="lit">8</span><span class="pun">;</span></code></li><li class="L7"><code class="language-java"><span class="pln">    n </span><span class="pun">|=</span><span class="pln"> n </span><span class="pun">&gt;&gt;&gt;</span><span class="pln"> </span><span class="lit">16</span><span class="pun">;</span></code></li><li class="L8"><code class="language-java"><span class="pln">    </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">(</span><span class="pln">n </span><span class="pun">&lt;</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln"> </span><span class="pun">?</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="pun">:</span><span class="pln"> </span><span class="pun">(</span><span class="pln">n </span><span class="pun">&gt;=</span><span class="pln"> MAXIMUM_CAPACITY</span><span class="pun">)</span><span class="pln"> </span><span class="pun">?</span><span class="pln"> MAXIMUM_CAPACITY </span><span class="pun">:</span><span class="pln"> n </span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pun">;</span></code></li><li class="L9"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><div class="md-section-divider"></div><h4 data-anchor-id="zv4x" id="线程安全">线程安全</h4><p data-anchor-id="bk4t">HashMap是非线程安全的，如果在多线程环境下，可以使用HashTable，HashTable中所有CRUD操作都是线程同步的，同样的，线程同步的代价就是效率变低了。</p><p data-anchor-id="e06g">再Java 5以后，有了一个线程安全的HashMap——ConcurrentHashMap，ConcurrentHashMap相对于HashTable来说，ConcurrentHashMap将hash表分为16个桶（默认值），诸如get,put,remove等常用操作只锁当前需要用到的桶。试想，原来只能一个线程进入，现在却能同时16个写线程进入（写线程才需要锁定，而读线程几乎不受限制，并发性的提升是显而易见。</p><div class="md-section-divider"></div><h4 data-anchor-id="pppl" id="快速失败fast-fail">快速失败(fast-fail)</h4><p data-anchor-id="ug7t">“快速失败”也就是fail-fast，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。</p><p data-anchor-id="7zzd">在HashMap的forEach方法中有以下代码：</p><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="8pd4"><ol class="linenums"><li class="L0"><code class="language-java"><span class="lit">@Override</span></code></li><li class="L1"><code class="language-java"><span class="kwd">public</span><span class="pln"> </span><span class="kwd">void</span><span class="pln"> forEach</span><span class="pun">(</span><span class="typ">BiConsumer</span><span class="pun">&lt;?</span><span class="pln"> </span><span class="kwd">super</span><span class="pln"> K</span><span class="pun">,</span><span class="pln"> </span><span class="pun">?</span><span class="pln"> </span><span class="kwd">super</span><span class="pln"> V</span><span class="pun">&gt;</span><span class="pln"> action</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L2"><code class="language-java"><span class="pln">    </span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;[]</span><span class="pln"> tab</span><span class="pun">;</span></code></li><li class="L3"><code class="language-java"><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">action </span><span class="pun">==</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span></code></li><li class="L4"><code class="language-java"><span class="pln">        </span><span class="kwd">throw</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">NullPointerException</span><span class="pun">();</span></code></li><li class="L5"><code class="language-java"><span class="pln">    </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">size </span><span class="pun">&gt;</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> </span><span class="pun">(</span><span class="pln">tab </span><span class="pun">=</span><span class="pln"> table</span><span class="pun">)</span><span class="pln"> </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L6"><code class="language-java"><span class="pln">        </span><span class="kwd">int</span><span class="pln"> mc </span><span class="pun">=</span><span class="pln"> modCount</span><span class="pun">;</span></code></li><li class="L7"><code class="language-java"><span class="pln">        </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;</span><span class="pln"> tab</span><span class="pun">.</span><span class="pln">length</span><span class="pun">;</span><span class="pln"> </span><span class="pun">++</span><span class="pln">i</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span></code></li><li class="L8"><code class="language-java"><span class="pln">            </span><span class="kwd">for</span><span class="pln"> </span><span class="pun">(</span><span class="typ">Node</span><span class="pun">&lt;</span><span class="pln">K</span><span class="pun">,</span><span class="pln">V</span><span class="pun">&gt;</span><span class="pln"> e </span><span class="pun">=</span><span class="pln"> tab</span><span class="pun">[</span><span class="pln">i</span><span class="pun">];</span><span class="pln"> e </span><span class="pun">!=</span><span class="pln"> </span><span class="kwd">null</span><span class="pun">;</span><span class="pln"> e </span><span class="pun">=</span><span class="pln"> e</span><span class="pun">.</span><span class="pln">next</span><span class="pun">)</span></code></li><li class="L9"><code class="language-java"><span class="pln">                action</span><span class="pun">.</span><span class="pln">accept</span><span class="pun">(</span><span class="pln">e</span><span class="pun">.</span><span class="pln">key</span><span class="pun">,</span><span class="pln"> e</span><span class="pun">.</span><span class="pln">value</span><span class="pun">);</span></code></li><li class="L0"><code class="language-java"><span class="pln">        </span><span class="pun">}</span></code></li><li class="L1"><code class="language-java"><span class="pln">        </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">modCount </span><span class="pun">!=</span><span class="pln"> mc</span><span class="pun">)</span></code></li><li class="L2"><code class="language-java"><span class="pln">            </span><span class="kwd">throw</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ConcurrentModificationException</span><span class="pun">();</span></code></li><li class="L3"><code class="language-java"><span class="pln">    </span><span class="pun">}</span></code></li><li class="L4"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="u4kt">在上面我们说到，modCount是记录每次HashMap结构修改。 <br>
forEach方法会在在进入for循环之前，将modCount赋值给mc，如果在for循环之后，HashMap的结构变化了，那么导致的结果就是modCount != mc，则抛出ConcurrentModificationException()异常。</p><div class="md-section-divider"></div><h4 data-anchor-id="3rdw" id="总结-1">总结</h4><ol data-anchor-id="5ibt">
<li>什么时候会使用HashMap？他有什么特点？ <br>
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。</li>
<li>你知道HashMap的工作原理吗？ <br>
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。</li>
<li>你知道get和put的原理吗？equals()和hashCode()的都有什么作用？ <br>
通过对key的hashCode()进行hashing，并计算下标( n-1 &amp; hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点</li>
<li>你知道hash的实现吗？为什么要这样实现？ <br>
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h &gt;&gt;&gt; 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。</li>
<li>如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？ <br>
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。</li>
</ol><hr><blockquote data-anchor-id="9gbs" class="white-blockquote">
  <p>前段时间因为找工作的缘故背了一些关于HashMap的面试题，死记硬背，也不是很懂，最近看了源码，很多知识才变的清晰，而且看源码挺有趣的。再接再厉。</p>
</blockquote><div class="md-section-divider"></div><h3 data-anchor-id="9s0p" id="java集合框架是什么说出一些集合框架的优点">Java集合框架是什么？说出一些集合框架的优点？</h3><p data-anchor-id="goyj">每种编程语言中都有集合。集合框架的部分优点如下： <br>
（1）使用核心集合类降低开发成本，而非实现我们自己的集合类。 <br>
（2）随着使用经过严格测试的集合框架类，代码质量会得到提高。 <br>
（3）通过使用JDK附带的集合类，可以降低代码维护成本。 <br>
（4）复用性和可操作性。</p><div class="md-section-divider"></div><h3 data-anchor-id="fx4q" id="集合框架中的泛型有什么优点">集合框架中的泛型有什么优点？</h3><p data-anchor-id="kczv">Java1.5引入了泛型，所有的集合接口和实现都大量地使用它。</p><p data-anchor-id="dgue">泛型允许我们为集合提供一个可以容纳的对象类型，因此，如果你添加其它类型的任何元素，它会在编译时报错。这避免了在运行时出现ClassCastException，因为你将会在编译时得到报错信息。泛型也使得代码整洁，我们不需要使用显式转换和instanceOf操作符。它也给运行时带来好处，因为不会产生类型检查的字节码指令。</p><div class="md-section-divider"></div><h3 data-anchor-id="er39" id="java集合框架的基础接口有哪些">Java集合框架的基础接口有哪些？</h3><p data-anchor-id="t0xn">Collection为集合层级的根接口。一个集合代表一组对象，这些对象即为它的元素。Java平台不提供这个接口任何直接的实现。</p><p data-anchor-id="7dbj">Set是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模，被用来代表集合，就如一副牌。</p><p data-anchor-id="cau7">List是一个有序集合，可以包含重复元素。你可以通过它的索引来访问任何元素。List更像长度动态变换的数组。</p><p data-anchor-id="g267">Map是一个将key映射到value的对象.一个Map不能包含重复的key：每个key最多只能映射一个value。</p><p data-anchor-id="fuop">一些其它的接口有Queue、Dequeue、SortedSet、SortedMap和ListIterator。</p><div class="md-section-divider"></div><h3 data-anchor-id="ma4t" id="为何collection不从cloneable和serializable接口继承">为何Collection不从Cloneable和Serializable接口继承？</h3><p data-anchor-id="2qnw">克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。</p><div class="md-section-divider"></div><h3 data-anchor-id="fxew" id="为何map接口不继承collection接口">为何Map接口不继承Collection接口？</h3><p data-anchor-id="2hgf">尽管Map接口和它的实现也是集合框架的一部分，但Map不是集合，集合也不是Map。因此，Map继承Collection毫无意义，反之亦然。</p><p data-anchor-id="kzdg">如果Map继承Collection接口，那么元素去哪儿？Map包含key-value对，它提供抽取key或value列表集合的方法，但是它不适合“一组对象”规范。</p><div class="md-section-divider"></div><h3 data-anchor-id="49n9" id="iterator是什么">Iterator是什么？</h3><p data-anchor-id="6ehn">Iterator接口提供遍历任何Collection的接口。我们可以从一个Collection中使用迭代器方法来获取迭代器实例。迭代器取代了Java集合框架中的Enumeration。迭代器允许调用者在迭代过程中移除元素。</p><div class="md-section-divider"></div><h3 data-anchor-id="ek98" id="iterator和listiterator的区别是什么">Iterator和ListIterator的区别是什么？</h3><p data-anchor-id="rsq6">下面列出了他们的区别： <br>
Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。 <br>
Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。 <br>
ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。</p><div class="md-section-divider"></div><h3 data-anchor-id="mnjd" id="enumeration和iterator接口的区别">Enumeration和Iterator接口的区别？</h3><p data-anchor-id="bt95">Enumeration速度是Iterator的2倍，同时占用更少的内存。但是，Iterator远远比Enumeration安全，因为其他线程不能够修改正在被iterator遍历的集合里面的对象。同时，Iterator允许调用者删除底层集合里面的元素，这对Enumeration来说是不可能的。</p><div class="md-section-divider"></div><h3 data-anchor-id="s2lv" id="为何没有像iteratoradd这样的方法向集合中添加元素">为何没有像Iterator.add()这样的方法，向集合中添加元素？</h3><p data-anchor-id="owb4">语义不明，已知的是，Iterator的协议不能确保迭代的次序。然而要注意，ListIterator没有提供一个add操作，它要确保迭代的顺序。</p><div class="md-section-divider"></div><h3 data-anchor-id="5zy2" id="为何迭代器没有一个方法可以直接获取下一个元素而不需要移动游标">为何迭代器没有一个方法可以直接获取下一个元素，而不需要移动游标？</h3><p data-anchor-id="wexj">它可以在当前Iterator的顶层实现，但是它用得很少，如果将它加到接口中，每个继承都要去实现它，这没有意义。</p><div class="md-section-divider"></div><h3 data-anchor-id="js8x" id="iterater和listiterator之间有什么区别">Iterater和ListIterator之间有什么区别？</h3><p data-anchor-id="li7t">（1）我们可以使用Iterator来遍历Set和List集合，而ListIterator只能遍历List。</p><p data-anchor-id="88i5">（2）Iterator只可以向前遍历，而LIstIterator可以双向遍历。</p><p data-anchor-id="a0zt">（3）ListIterator从Iterator接口继承，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。</p><div class="md-section-divider"></div><h3 data-anchor-id="pawy" id="遍历一个list有哪些不同的方式">遍历一个List有哪些不同的方式？</h3><div class="md-section-divider"></div><pre class="prettyprint linenums prettyprinted" data-anchor-id="zgd6"><ol class="linenums"><li class="L0"><code class="language-java"><span class="typ">List</span><span class="pun">&lt;</span><span class="typ">String</span><span class="pun">&gt;</span><span class="pln"> strList </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">new</span><span class="pln"> </span><span class="typ">ArrayList</span><span class="pun">&lt;&gt;();</span></code></li><li class="L1"><code class="language-java"><span class="com">//使用for-each循环</span></code></li><li class="L2"><code class="language-java"><span class="kwd">for</span><span class="pun">(</span><span class="typ">String</span><span class="pln"> obj </span><span class="pun">:</span><span class="pln"> strList</span><span class="pun">){</span></code></li><li class="L3"><code class="language-java"><span class="pln">  </span><span class="typ">System</span><span class="pun">.</span><span class="pln">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="pln">obj</span><span class="pun">);</span></code></li><li class="L4"><code class="language-java"><span class="pun">}</span></code></li><li class="L5"><code class="language-java"><span class="com">//using iterator</span></code></li><li class="L6"><code class="language-java"><span class="typ">Iterator</span><span class="pun">&lt;</span><span class="typ">String</span><span class="pun">&gt;</span><span class="pln"> it </span><span class="pun">=</span><span class="pln"> strList</span><span class="pun">.</span><span class="pln">iterator</span><span class="pun">();</span></code></li><li class="L7"><code class="language-java"><span class="kwd">while</span><span class="pun">(</span><span class="pln">it</span><span class="pun">.</span><span class="pln">hasNext</span><span class="pun">()){</span></code></li><li class="L8"><code class="language-java"><span class="pln">  </span><span class="typ">String</span><span class="pln"> obj </span><span class="pun">=</span><span class="pln"> it</span><span class="pun">.</span><span class="pln">next</span><span class="pun">();</span></code></li><li class="L9"><code class="language-java"><span class="pln">  </span><span class="typ">System</span><span class="pun">.</span><span class="pln">out</span><span class="pun">.</span><span class="pln">println</span><span class="pun">(</span><span class="pln">obj</span><span class="pun">);</span></code></li><li class="L0"><code class="language-java"><span class="pun">}</span></code></li></ol></pre><p data-anchor-id="9ot5">使用迭代器更加线程安全，因为它可以确保，在当前遍历的集合元素被更改的时候，它会抛出ConcurrentModificationException。</p><div class="md-section-divider"></div><h3 data-anchor-id="ucr1" id="通过迭代器fail-fast属性你明白了什么">通过迭代器fail-fast属性，你明白了什么？</h3><p data-anchor-id="z9un">每次我们尝试获取下一个元素的时候，Iterator fail-fast属性检查当前集合结构里的任何改动。如果发现任何改动，它抛出ConcurrentModificationException。Collection中所有Iterator的实现都是按fail-fast来设计的（ConcurrentHashMap和CopyOnWriteArrayList这类并发集合类除外）。</p><div class="md-section-divider"></div><h3 data-anchor-id="czdy" id="fail-fast与fail-safe有什么区别">fail-fast与fail-safe有什么区别？</h3><p data-anchor-id="piuq">Iterator的安全失败是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。java.util包下面的所有的集合类都是快速失败的，而java.util.concurrent包下面的所有的类都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常。</p><div class="md-section-divider"></div><h3 data-anchor-id="c97v" id="在迭代一个集合的时候如何避免concurrentmodificationexception">在迭代一个集合的时候，如何避免ConcurrentModificationException？</h3><p data-anchor-id="er7q">在遍历一个集合的时候，我们可以使用并发集合类来避免ConcurrentModificationException，比如使用CopyOnWriteArrayList，而不是ArrayList。</p><div class="md-section-divider"></div><h3 data-anchor-id="1hur" id="为何iterator接口没有具体的实现">为何Iterator接口没有具体的实现？</h3><p data-anchor-id="mkng">Iterator接口定义了遍历集合的方法，但它的实现则是集合实现类的责任。每个能够返回用于遍历的Iterator的集合类都有它自己的Iterator实现内部类。</p><p data-anchor-id="vine">这就允许集合类去选择迭代器是fail-fast还是fail-safe的。比如，ArrayList迭代器是fail-fast的，而CopyOnWriteArrayList迭代器是fail-safe的。</p><div class="md-section-divider"></div><h3 data-anchor-id="z07g" id="unsupportedoperationexception是什么">UnsupportedOperationException是什么？</h3><p data-anchor-id="v71x">UnsupportedOperationException是用于表明操作不支持的异常。在JDK类中已被大量运用，在集合框架java.util.Collections.UnmodifiableCollection将会在所有add和remove操作中抛出这个异常。</p><div class="md-section-divider"></div><h3 data-anchor-id="4qdl" id="在java中hashmap是如何工作的">在Java中，HashMap是如何工作的？</h3><p data-anchor-id="12l0">HashMap在Map.Entry静态内部类实现中存储key-value对。HashMap使用哈希算法，在put和get方法中，它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候，HashMap使用Key hashCode()和哈希算法来找出存储key-value对的索引。Entry存储在LinkedList中，所以如果存在entry，它使用equals()方法来检查传递的key是否已经存在，如果存在，它会覆盖value，如果不存在，它会创建一个新的entry然后保存。当我们通过传递key调用get方法时，它再次使用hashCode()来找到数组中的索引，然后使用equals()方法找出正确的Entry，然后返回它的值。下面的图片解释了详细内容。</p><p data-anchor-id="lbpf">其它关于HashMap比较重要的问题是容量、负荷系数和阀值调整。HashMap默认的初始容量是32，负荷系数是0.75。阀值是为负荷系数乘以容量，无论何时我们尝试添加一个entry，如果map的大小比阀值大的时候，HashMap会对map的内容进行重新哈希，且使用更大的容量。容量总是2的幂，所以如果你知道你需要存储大量的key-value对，比如缓存从数据库里面拉取的数据，使用正确的容量和负荷系数对HashMap进行初始化是个不错的做法。</p><div class="md-section-divider"></div><h3 data-anchor-id="hpbt" id="hashcode和equals方法有何重要性">hashCode()和equals()方法有何重要性？</h3><p data-anchor-id="2j89">HashMap使用Key对象的hashCode()和equals()方法去决定key-value对的索引。当我们试着从HashMap中获取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，在这种情况下，两个不同Key也许会产生相同的hashCode()和equals()输出，HashMap将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方。同样的，所有不允许存储重复数据的集合类都使用hashCode()和equals()去查找重复，所以正确实现它们非常重要。equals()和hashCode()的实现应该遵循以下规则：</p><p data-anchor-id="yl24">（1）如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。</p><p data-anchor-id="flyy">（2）如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。</p><div class="md-section-divider"></div><h3 data-anchor-id="279x" id="我们能否使用任何类作为map的key">我们能否使用任何类作为Map的key？</h3><p data-anchor-id="b2vc">我们可以使用任何类作为Map的key，然而在使用它们之前，需要考虑以下几点：</p><p data-anchor-id="tp7t">（1）如果类重写了equals()方法，它也应该重写hashCode()方法。</p><p data-anchor-id="mofq">（2）类的所有实例需要遵循与equals()和hashCode()相关的规则。请参考之前提到的这些规则。</p><p data-anchor-id="h7o4">（3）如果一个类没有使用equals()，你不应该在hashCode()中使用它。</p><p data-anchor-id="s7fx">（4）用户自定义key类的最佳实践是使之为不可变的，这样，hashCode()值可以被缓存起来，拥有更好的性能。不可变的类也可以确保hashCode()和equals()在未来不会改变，这样就会解决与可变相关的问题了。</p><p data-anchor-id="exd3">比如，我有一个类MyKey，在HashMap中使用它。</p><p data-anchor-id="rbyd">//传递给MyKey的name参数被用于equals()和hashCode()中 <br>
MyKey key = new MyKey('Pankaj'); //assume hashCode=1234 <br>
myHashMap.put(key, 'Value'); <br>
// 以下的代码会改变key的hashCode()和equals()值 <br>
key.setName('Amit'); //assume new hashCode=7890 <br>
//下面会返回null，因为HashMap会尝试查找存储同样索引的key，而key已被改变了，匹配失败，返回null <br>
myHashMap.get(new MyKey('Pankaj')); <br>
那就是为何String和Integer被作为HashMap的key大量使用。</p><div class="md-section-divider"></div><h3 data-anchor-id="t0cq" id="map接口提供了哪些不同的集合视图">Map接口提供了哪些不同的集合视图？</h3><p data-anchor-id="9nix">Map接口提供三个集合视图：</p><p data-anchor-id="8pbs">（1）Set keyset()：返回map中包含的所有key的一个Set视图。集合是受map支持的，map的变化会在集合中反映出来，反之亦然。当一个迭代器正在遍历一个集合时，若map被修改了（除迭代器自身的移除操作以外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。</p><p data-anchor-id="n5b9">（2）Collection values()：返回一个map中包含的所有value的一个Collection视图。这个collection受map支持的，map的变化会在collection中反映出来，反之亦然。当一个迭代器正在遍历一个collection时，若map被修改了（除迭代器自身的移除操作以外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。</p><p data-anchor-id="q8r8">（3）Set&gt; entrySet()：返回一个map钟包含的所有映射的一个集合视图。这个集合受map支持的，map的变化会在collection中反映出来，反之亦然。当一个迭代器正在遍历一个集合时，若map被修改了（除迭代器自身的移除操作，以及对迭代器返回的entry进行setValue外），迭代器的结果会变为未定义。集合支持通过Iterator的Remove、Set.remove、removeAll、retainAll和clear操作进行元素移除，从map中移除对应的映射。它不支持add和addAll操作。</p><div class="md-section-divider"></div><h3 data-anchor-id="9133" id="hashmap和hashtable有何不同">HashMap和HashTable有何不同？</h3><p data-anchor-id="0vui">（1）HashMap允许key和value为null，而HashTable不允许。</p><p data-anchor-id="6jno">（2）HashTable是同步的，而HashMap不是。所以HashMap适合单线程环境，HashTable适合多线程环境。</p><p data-anchor-id="6xem">（3）在Java1.4中引入了LinkedHashMap，HashMap的一个子类，假如你想要遍历顺序，你很容易从HashMap转向LinkedHashMap，但是HashTable不是这样的，它的顺序是不可预知的。</p><p data-anchor-id="b72z">（4）HashMap提供对key的Set进行遍历，因此它是fail-fast的，但HashTable提供对key的Enumeration进行遍历，它不支持fail-fast。</p><p data-anchor-id="6yi1">（5）HashTable被认为是个遗留的类，如果你寻求在迭代的时候修改Map，你应该使用CocurrentHashMap。</p><div class="md-section-divider"></div><h3 data-anchor-id="zlk2" id="如何决定选用hashmap还是treemap">如何决定选用HashMap还是TreeMap？</h3><p data-anchor-id="fk2i">对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。</p><div class="md-section-divider"></div><h3 data-anchor-id="9cj3" id="arraylist和vector有何异同点">ArrayList和Vector有何异同点？</h3><p data-anchor-id="d34e">ArrayList和Vector在很多时候都很类似。</p><p data-anchor-id="res7">（1）两者都是基于索引的，内部由一个数组支持。</p><p data-anchor-id="ukys">（2）两者维护插入的顺序，我们可以根据插入顺序来获取元素。</p><p data-anchor-id="x474">（3）ArrayList和Vector的迭代器实现都是fail-fast的。</p><p data-anchor-id="e1ms">（4）ArrayList和Vector两者允许null值，也可以使用索引值对元素进行随机访问。</p><p data-anchor-id="48mt">以下是ArrayList和Vector的不同点。</p><p data-anchor-id="quee">（1）Vector是同步的，而ArrayList不是。然而，如果你寻求在迭代的时候对列表进行改变，你应该使用CopyOnWriteArrayList。</p><p data-anchor-id="euwf">（2）ArrayList比Vector快，它因为有同步，不会过载。</p><p data-anchor-id="eeub">（3）ArrayList更加通用，因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。</p><div class="md-section-divider"></div><h3 data-anchor-id="wtmt" id="array和arraylist有何区别什么时候更适合用array">Array和ArrayList有何区别？什么时候更适合用Array？</h3><p data-anchor-id="6gnt">Array可以容纳基本类型和对象，而ArrayList只能容纳对象。</p><p data-anchor-id="5yxo">Array是指定大小的，而ArrayList大小是固定的。</p><p data-anchor-id="4zb5">Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。尽管ArrayList明显是更好的选择，但也有些时候Array比较好用。</p><p data-anchor-id="24md">（1）如果列表的大小已经指定，大部分情况下是存储和遍历它们。</p><p data-anchor-id="zl2j">（2）对于遍历基本数据类型，尽管Collections使用自动装箱来减轻编码任务，在指定大小的基本类型的列表上工作也会变得很慢。</p><p data-anchor-id="d1m3">（3）如果你要使用多维数组，使用[][]比List&gt;更容易。</p><div class="md-section-divider"></div><h3 data-anchor-id="s8qa" id="arraylist和linkedlist有何区别">ArrayList和LinkedList有何区别？</h3><p data-anchor-id="n480">ArrayList和LinkedList两者都实现了List接口，但是它们之间有些不同。</p><p data-anchor-id="57ob">（1）ArrayList是由Array所支持的基于一个索引的数据结构，所以它提供对元素的随机访问，复杂度为O(1)，但LinkedList存储一系列的节点数据，每个节点都与前一个和下一个节点相连接。所以，尽管有使用索引获取元素的方法，内部实现是从起始点开始遍历，遍历到索引的节点然后返回元素，时间复杂度为O(n)，比ArrayList要慢。</p><p data-anchor-id="bb8h">（2）与ArrayList相比，在LinkedList中插入、添加和删除一个元素会更快，因为在一个元素被插入到中间的时候，不会涉及改变数组的大小，或更新索引。</p><p data-anchor-id="u8b5">（3）LinkedList比ArrayList消耗更多的内存，因为LinkedList中的每个节点存储了前后节点的引用。</p><div class="md-section-divider"></div><h3 data-anchor-id="4rmc" id="哪些集合类提供对元素的随机访问">哪些集合类提供对元素的随机访问？</h3><p data-anchor-id="6q2j">ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。</p><div class="md-section-divider"></div><h3 data-anchor-id="gpqh" id="enumset是什么">EnumSet是什么？</h3><p data-anchor-id="fkyo">java.util.EnumSet是使用枚举类型的集合实现。当集合创建时，枚举集合中的所有元素必须来自单个指定的枚举类型，可以是显示的或隐示的。EnumSet是不同步的，不允许值为null的元素。它也提供了一些有用的方法，比如copyOf(Collection c)、of(E first,E…rest)和complementOf(EnumSet s)。</p><div class="md-section-divider"></div><h3 data-anchor-id="ndty" id="哪些集合类是线程安全的">哪些集合类是线程安全的？</h3><p data-anchor-id="hek3">Vector、HashTable、Properties和Stack是同步类，所以它们是线程安全的，可以在多线程环境下使用。Java1.5并发API包括一些集合类，允许迭代时修改，因为它们都工作在集合的克隆上，所以它们在多线程环境中是安全的。</p><div class="md-section-divider"></div><h3 data-anchor-id="uwh0" id="并发集合类是什么">并发集合类是什么？</h3><p data-anchor-id="xqdb">Java1.5并发包（java.util.concurrent）包含线程安全集合类，允许在迭代时修改集合。迭代器被设计为fail-fast的，会抛出ConcurrentModificationException。一部分类为：CopyOnWriteArrayList、 ConcurrentHashMap、CopyOnWriteArraySet。</p><div class="md-section-divider"></div><h3 data-anchor-id="vudr" id="blockingqueue是什么">BlockingQueue是什么？</h3><p data-anchor-id="mly8">Java.util.concurrent.BlockingQueue是一个队列，在进行检索或移除一个元素的时候，它会等待队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。</p><p data-anchor-id="iq72">BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间，或消费者有可用的对象，因为它都在BlockingQueue的实现类中被处理了。</p><p data-anchor-id="vr5a">Java提供了集中BlockingQueue的实现，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。</p><div class="md-section-divider"></div><h3 data-anchor-id="c7w3" id="队列和栈是什么列出它们的区别">队列和栈是什么，列出它们的区别？</h3><p data-anchor-id="i4x9">栈和队列两者都被用来预存储数据。 <br>
java.util.Queue是一个接口，它的实现类在Java并发包中。队列允许先进先出（FIFO）检索元素，但并非总是这样。Deque接口允许从两端检索元素。</p><p data-anchor-id="qhhm">栈与队列很相似，但它允许对元素进行后进先出（LIFO）进行检索。</p><p data-anchor-id="u3qq">Stack是一个扩展自Vector的类，而Queue是一个接口。</p><div class="md-section-divider"></div><h3 data-anchor-id="tjzt" id="collections类是什么">Collections类是什么？</h3><p data-anchor-id="atiq">Java.util.Collections是一个工具类仅包含静态方法，它们操作或返回集合。它包含操作集合的多态算法，返回一个由指定集合支持的新集合和其它一些内容。这个类包含集合框架算法的方法，比如折半搜索、排序、混编和逆序等。</p><div class="md-section-divider"></div><h3 data-anchor-id="8ewh" id="comparable和comparator接口是什么">Comparable和Comparator接口是什么？</h3><p data-anchor-id="ofbv">如果我们想使用Array或Collection的排序方法时，需要在自定义类里实现Java提供Comparable接口。</p><p data-anchor-id="1m5d">Comparable接口有compareTo(T OBJ)方法，它被排序方法所使用。我们应该重写这个方法，如果“this”对象比传递的对象参数更小、相等或更大时，它返回一个负整数、0或正整数。</p><p data-anchor-id="coey">但是，在大多数实际情况下，我们想根据不同参数进行排序。</p><p data-anchor-id="9pvv">比如，作为一个CEO，我想对雇员基于薪资进行排序，一个HR想基于年龄对他们进行排序。这就是我们需要使用Comparator接口的情景，因为Comparable.compareTo(Object o)方法实现只能基于一个字段进行排序，我们不能根据对象排序的需要选择字段。</p><p data-anchor-id="t5j4">Comparator接口的compare(Object o1, Object o2)方法的实现需要传递两个对象参数，若第一个参数比第二个小，返回负整数；若第一个等于第二个，返回0；若第一个比第二个大，返回正整数。</p><div class="md-section-divider"></div><h3 data-anchor-id="afre" id="comparable和comparator接口有何区别">Comparable和Comparator接口有何区别？</h3><p data-anchor-id="q714">Comparable和Comparator接口被用来对对象集合或者数组进行排序。</p><p data-anchor-id="ir3l">Comparable接口被用来提供对象的自然排序，我们可以使用它来提供基于单个逻辑的排序。</p><p data-anchor-id="nn0g">Comparator接口被用来提供不同的排序算法，我们可以选择需要使用的Comparator来对给定的对象集合进行排序。</p><div class="md-section-divider"></div><h3 data-anchor-id="crdv" id="我们如何对一组对象进行排序">我们如何对一组对象进行排序？</h3><p data-anchor-id="jmea">如果我们需要对一个对象数组进行排序，我们可以使用Arrays.sort()方法。如果我们需要排序一个对象列表，我们可以使用Collection.sort()方法。两个类都有用于自然排序（使用Comparable）或基于标准的排序（使用Comparator）的重载方法sort()。Collections内部使用数组排序方法，所有它们两者都有相同的性能，只是Collections需要花时间将列表转换为数组。</p><div class="md-section-divider"></div><h3 data-anchor-id="zwav" id="当一个集合被作为参数传递给一个函数时如何才可以确保函数不能修改它">当一个集合被作为参数传递给一个函数时，如何才可以确保函数不能修改它？</h3><p data-anchor-id="f3oh">在作为参数传递之前，我们可以使用Collections.unmodifiableCollection(Collection c)方法创建一个只读集合，这将确保改变集合的任何操作都会抛出UnsupportedOperationException。</p><div class="md-section-divider"></div><h3 data-anchor-id="fcn4" id="我们如何从给定集合那里创建一个synchronized的集合">我们如何从给定集合那里创建一个synchronized的集合？</h3><p data-anchor-id="m9wk">我们可以使用Collections.synchronizedCollection(Collection c)根据指定集合来获取一个synchronized（线程安全的）集合。</p><div class="md-section-divider"></div><h3 data-anchor-id="ge92" id="集合框架里实现的通用算法有哪些">集合框架里实现的通用算法有哪些？</h3><p data-anchor-id="iikw">Java集合框架提供常用的算法实现，比如排序和搜索。Collections类包含这些方法实现。大部分算法是操作List的，但一部分对所有类型的集合都是可用的。部分算法有排序、搜索、混编、最大最小值。</p><div class="md-section-divider"></div><h3 data-anchor-id="ppk9" id="大写的o是什么举几个例子">大写的O是什么？举几个例子？</h3><p data-anchor-id="5j4y">大写的O描述的是，就数据结构中的一系列元素而言，一个算法的性能。Collection类就是实际的数据结构，我们通常基于时间、内存和性能，使用大写的O来选择集合实现。</p><p data-anchor-id="09dh">比如： <br>
例子1：ArrayList的get(index i)是一个常量时间操作，它不依赖list中元素的数量。所以它的性能是O(1)。</p><p data-anchor-id="rd2n">例子2：一个对于数组或列表的线性搜索的性能是O(n)，因为我们需要遍历所有的元素来查找需要的元素。</p><div class="md-section-divider"></div><h3 data-anchor-id="zsgq" id="与java集合框架相关的有哪些最好的实践">与Java集合框架相关的有哪些最好的实践？</h3><p data-anchor-id="kjt0">（1）根据需要选择正确的集合类型。比如，如果指定了大小，我们会选用Array而非ArrayList。如果我们想根据插入顺序遍历一个Map，我们需要使用TreeMap。如果我们不想重复，我们应该使用Set。</p><p data-anchor-id="tiny">（2）一些集合类允许指定初始容量，所以如果我们能够估计到存储元素的数量，我们可以使用它，就避免了重新哈希或大小调整。</p><p data-anchor-id="j91t">（3）基于接口编程，而非基于实现编程，它允许我们后来轻易地改变实现。</p><p data-anchor-id="ykv2">（4）总是使用类型安全的泛型，避免在运行时出现ClassCastException。</p><p data-anchor-id="yivb">（5）使用JDK提供的不可变类作为Map的key，可以避免自己实现hashCode()和equals()。</p><p data-anchor-id="j2kv">（6）尽可能使用Collections工具类，或者获取只读、同步或空的集合，而非编写自己的实现。它将会提供代码重用性，它有着更好的稳定性和可维护性。</p><div class="md-section-divider"></div><h3 data-anchor-id="fo2b" id="treemap和treeset在排序时如何比较元素collections工具类中的sort方法如何比较元素">TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？</h3><p data-anchor-id="4806">答：TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。 </p><div class="md-section-divider"></div><h3 data-anchor-id="yzd3" id="结束">结束</h3></div>
</body>
</html>